package BFS解决FloodFill算法;

import java.util.LinkedList;
import java.util.Queue;

public class 被围绕的区域 {

    int [] dx = {0,0,1,-1};
    int [] dy = {1,-1,0,0};
    int m,n;
    public void solve(char[][] board)
    {
        m = board.length;
        n = board[0].length;

        //1.先处理边界的 “O”取通块，全部修改成 “.”
        for(int j  = 0 ; j < m ; j++)
        {
            if(board[j][0] == 'O')
            {
                bfs(board,j,0);
            }
            if(board[j][n-1] == 'O')
            {
                bfs(board,j,n-1);
            }

        }
        for(int  k = 0 ; k<n ; k++)
        {
            if(board[0][k] == 'O')
            {
                bfs(board,0,k);
            }
            if(board[m-1][k] == 'O')
            {
                bfs(board,m-1,k);
            }
        }
        // 2. 还原
        for(int i = 0; i<m ; i++)
        {
            for(int j = 0 ; j<n;j++)
            {
                if(board[i][j] == 'O')
                {
                    board[i][j] = 'X';
                }
                else if(board[i][j] == '.')
                {
                    board[i][j] = 'O';
                }
            }
        }

    }

    public void bfs(char[][] board,int xx ,int yy)
    {
        Queue<int []> q= new LinkedList<>();
        board[xx][yy] = '.';
        q.offer(new int[]{xx,yy});

        while(!q.isEmpty())
        {
            int[] a = q.poll();
            for(int i = 0;i<4;i++)
            {
                int x = a[0]+dx[i];
                int y = a[1]+dy[i];
                if(x>0 && x<m && y>0 && y<n && board[x][y] == 'O')
                {
                    board[x][y] = '.';
                    q.offer(new int[]{x,y});
                }
            }
        }
    }
}
